<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
  <title>穷举搜索 - lclei blog</title>
  <meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">


<meta name="author" content="lclei" /><meta name="description" content="实质是创建一个状态树，边建立边剪枝，得到最终状态输出 步骤有：
 列出表示状态的数据结构 列出在状态之间迁移的动作的数据结构 列出两个状态转换的所有动作列表 创建一个deque存储搜索的状态 从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction 判断新状态是否有效，有效则加入deque，继续递归调用搜索 " /><meta name="keywords" content="lclei, blog, code" />






<meta name="generator" content="Hugo 0.68.3 with theme even" />


<link rel="canonical" href="http://localhost:1313/post/%E7%A9%B7%E4%B8%BE%E6%90%9C%E7%B4%A2/" />
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/manifest.json">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">



<link href="/sass/main.min.2e81bbed97b8b282c1aeb57488cc71c8d8c8ec559f3931531bd396bf31e0d4dd.css" rel="stylesheet">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.1.20/dist/jquery.fancybox.min.css" integrity="sha256-7TyXnr2YU040zfSP+rEcz29ggW4j56/ujTPwjMzyqFY=" crossorigin="anonymous">


<meta property="og:title" content="穷举搜索" />
<meta property="og:description" content="实质是创建一个状态树，边建立边剪枝，得到最终状态输出
步骤有：

列出表示状态的数据结构
列出在状态之间迁移的动作的数据结构
列出两个状态转换的所有动作列表
创建一个deque存储搜索的状态
从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction
判断新状态是否有效，有效则加入deque，继续递归调用搜索
" />
<meta property="og:type" content="article" />
<meta property="og:url" content="http://localhost:1313/post/%E7%A9%B7%E4%B8%BE%E6%90%9C%E7%B4%A2/" />
<meta property="article:published_time" content="2019-12-08T00:00:00+00:00" />
<meta property="article:modified_time" content="2019-12-08T00:00:00+00:00" />
<meta itemprop="name" content="穷举搜索">
<meta itemprop="description" content="实质是创建一个状态树，边建立边剪枝，得到最终状态输出
步骤有：

列出表示状态的数据结构
列出在状态之间迁移的动作的数据结构
列出两个状态转换的所有动作列表
创建一个deque存储搜索的状态
从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction
判断新状态是否有效，有效则加入deque，继续递归调用搜索
">
<meta itemprop="datePublished" content="2019-12-08T00:00:00&#43;00:00" />
<meta itemprop="dateModified" content="2019-12-08T00:00:00&#43;00:00" />
<meta itemprop="wordCount" content="1305">



<meta itemprop="keywords" content="algorithm,cpp," /><meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content="穷举搜索"/>
<meta name="twitter:description" content="实质是创建一个状态树，边建立边剪枝，得到最终状态输出
步骤有：

列出表示状态的数据结构
列出在状态之间迁移的动作的数据结构
列出两个状态转换的所有动作列表
创建一个deque存储搜索的状态
从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction
判断新状态是否有效，有效则加入deque，继续递归调用搜索
"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->

</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/" class="logo">lclei</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <a href="/">
        <li class="mobile-menu-item">Home</li>
      </a><a href="/post/">
        <li class="mobile-menu-item">Archives</li>
      </a><a href="/tags/">
        <li class="mobile-menu-item">Tags</li>
      </a><a href="/categories/">
        <li class="mobile-menu-item">Categories</li>
      </a><a href="/about/">
        <li class="mobile-menu-item">About</li>
      </a>
  </ul>

  


</nav>

  <div class="container" id="mobile-panel">
    <header id="header" class="header">
        <div class="logo-wrapper">
  <a href="/" class="logo">lclei</a>
</div>





<nav class="site-navbar">
  <ul id="menu" class="menu">
    <li class="menu-item">
        <a class="menu-item-link" href="/">Home</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/post/">Archives</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/tags/">Tags</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/categories/">Categories</a>
      </li><li class="menu-item">
        <a class="menu-item-link" href="/about/">About</a>
      </li>
  </ul>
</nav>

    </header>

    <main id="main" class="main">
      <div class="content-wrapper">
        <div id="content" class="content">
          <article class="post">
    
    <header class="post-header">
      <h1 class="post-title">穷举搜索</h1>

      <div class="post-meta">
        <span class="post-time"> 2019-12-08 </span>
        
        
      </div>
    </header>

    <div class="post-toc" id="post-toc">
  <h2 class="post-toc-title">Contents</h2>
  <div class="post-toc-content always-active">
    <nav id="TableOfContents"></nav>
  </div>
</div>
    <div class="post-content">
      <p>实质是创建一个状态树，边建立边剪枝，得到最终状态输出
步骤有：</p>
<ol>
<li>列出表示状态的数据结构</li>
<li>列出在状态之间迁移的动作的数据结构</li>
<li>列出两个状态转换的所有动作列表</li>
<li>创建一个deque存储搜索的状态</li>
<li>从deque尾端取出状态，判断是否是最终状态，是的话打印当前deque，进行搜索search，循环所有动作，执行动作searchOnOneAction</li>
<li>判断新状态是否有效，有效则加入deque，继续递归调用搜索</li>
</ol>
<p>有很多问题用到穷举搜索，比如过河问题</p>
<blockquote>
<p>三个和尚和三个妖怪过河
船只能载两个
任何时候只要妖怪数量大于和尚数量
妖怪就要吃掉和尚
求解过河方案</p>
</blockquote>
<p>这个问题首先确定状态的数据结构，状态就是两岸monk和monster的数量，同时有一些配套操作</p>
<ul>
<li>判断是否是最终状态</li>
<li>状态迁移</li>
<li>判断状态是否有效</li>
</ul>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">ItemState</span><span class="p">{</span>
<span class="k">friend</span>	<span class="n">ostream</span><span class="o">&amp;</span> <span class="k">operator</span><span class="o">&lt;&lt;</span><span class="p">(</span><span class="n">ostream</span><span class="o">&amp;</span><span class="p">,</span> <span class="k">const</span> <span class="n">ItemState</span><span class="o">&amp;</span><span class="p">);</span>
<span class="k">public</span><span class="o">:</span>
	<span class="kt">bool</span> <span class="k">operator</span><span class="o">==</span><span class="p">(</span><span class="k">const</span> <span class="n">ItemState</span><span class="o">&amp;</span><span class="p">);</span>
	<span class="kt">bool</span> <span class="nf">isFinalState</span><span class="p">();</span>
	<span class="kt">bool</span> <span class="nf">takeAction</span><span class="p">(</span><span class="n">ItemState</span><span class="o">&amp;</span> <span class="n">next</span><span class="p">,</span> <span class="k">const</span> <span class="n">ACTION_EFFECTION</span><span class="o">&amp;</span> <span class="n">action</span><span class="p">);</span>
	<span class="kt">bool</span> <span class="nf">isValid</span><span class="p">();</span>
	<span class="kt">int</span> <span class="n">local_monster</span><span class="p">;</span>
	<span class="kt">int</span> <span class="n">local_monk</span><span class="p">;</span>
	<span class="kt">int</span> <span class="n">remote_monster</span><span class="p">;</span>
	<span class="kt">int</span> <span class="n">remote_monk</span><span class="p">;</span>
	<span class="n">BOAT_LOCATION</span> <span class="n">boat</span><span class="p">;</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><p>动作有如下定义</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">typedef</span> <span class="k">enum</span><span class="p">{</span>
	<span class="n">ONE_MONSTER_GO</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span>
	<span class="n">TWO_MONSTER_GO</span><span class="p">,</span>
	<span class="n">ONE_MONK_GO</span><span class="p">,</span>
	<span class="n">TWO_MONK_GO</span><span class="p">,</span>
	<span class="n">ONR_MONSTER_ONE_MONK_GO</span><span class="p">,</span>
	<span class="n">ONE_MONSTER_BACK</span><span class="p">,</span>
	<span class="n">TWO_MONSTER_BACK</span><span class="p">,</span>
	<span class="n">ONE_MONK_BACK</span><span class="p">,</span>
	<span class="n">TWO_MONK_BACK</span><span class="p">,</span>
	<span class="n">ONR_MONSTER_ONE_MONK_BACK</span><span class="p">,</span>
	<span class="n">INVALID_ACTION_NAME</span><span class="p">,</span>
<span class="p">}</span><span class="n">ACTION_NAME</span><span class="p">;</span>	
	
<span class="k">typedef</span> <span class="k">struct</span><span class="p">{</span>
	<span class="n">ACTION_NAME</span> <span class="n">act</span><span class="p">;</span>
	<span class="n">BOAT_LOCATION</span> <span class="n">boat_to</span><span class="p">;</span>
	<span class="kt">int</span> <span class="n">move_monster</span><span class="p">;</span>
	<span class="kt">int</span> <span class="n">move_monk</span><span class="p">;</span>
<span class="p">}</span><span class="n">ACTION_EFFECTION</span><span class="p">;</span>
</code></pre></td></tr></table>
</div>
</div><p>得到action的列表，作为穷举的依据</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="n">ACTION_EFFECTION</span> <span class="n">actEffect</span><span class="p">[]</span> <span class="o">=</span>
<span class="p">{</span>
	<span class="p">{</span><span class="n">ONE_MONSTER_GO</span><span class="p">,</span>  			<span class="n">REMOTE</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">},</span>
	<span class="p">{</span><span class="n">TWO_MONSTER_GO</span><span class="p">,</span> 			<span class="n">REMOTE</span><span class="p">,</span>	<span class="o">-</span><span class="mi">2</span><span class="p">,</span>	<span class="mi">0</span><span class="p">},</span>
	<span class="p">{</span><span class="n">ONE_MONK_GO</span><span class="p">,</span>				<span class="n">REMOTE</span><span class="p">,</span>	<span class="mi">0</span><span class="p">,</span>	<span class="o">-</span><span class="mi">1</span><span class="p">},</span>
	<span class="p">{</span><span class="n">TWO_MONK_GO</span><span class="p">,</span>				<span class="n">REMOTE</span><span class="p">,</span>	<span class="mi">0</span><span class="p">,</span>	<span class="o">-</span><span class="mi">2</span><span class="p">},</span>
	<span class="p">{</span><span class="n">ONR_MONSTER_ONE_MONK_GO</span><span class="p">,</span>	<span class="n">REMOTE</span><span class="p">,</span>	<span class="o">-</span><span class="mi">1</span><span class="p">,</span>	<span class="o">-</span><span class="mi">1</span><span class="p">},</span>
	<span class="p">{</span><span class="n">ONE_MONSTER_BACK</span><span class="p">,</span>			<span class="n">LOCAL</span><span class="p">,</span>	<span class="mi">1</span><span class="p">,</span>	<span class="mi">0</span><span class="p">},</span>
	<span class="p">{</span><span class="n">TWO_MONSTER_BACK</span><span class="p">,</span>			<span class="n">LOCAL</span><span class="p">,</span>	<span class="mi">2</span><span class="p">,</span>	<span class="mi">0</span><span class="p">},</span>
	<span class="p">{</span><span class="n">ONE_MONK_BACK</span><span class="p">,</span>				<span class="n">LOCAL</span><span class="p">,</span>	<span class="mi">0</span><span class="p">,</span>	<span class="mi">1</span><span class="p">},</span>
	<span class="p">{</span><span class="n">TWO_MONK_BACK</span><span class="p">,</span>				<span class="n">LOCAL</span><span class="p">,</span>	<span class="mi">0</span><span class="p">,</span>	<span class="mi">2</span><span class="p">},</span>
	<span class="p">{</span><span class="n">ONR_MONSTER_ONE_MONK_BACK</span><span class="p">,</span>	<span class="n">LOCAL</span><span class="p">,</span>	<span class="mi">1</span><span class="p">,</span>	<span class="mi">1</span><span class="p">}</span>
<span class="p">};</span>
</code></pre></td></tr></table>
</div>
</div><p>搜索时</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt"> 1
</span><span class="lnt"> 2
</span><span class="lnt"> 3
</span><span class="lnt"> 4
</span><span class="lnt"> 5
</span><span class="lnt"> 6
</span><span class="lnt"> 7
</span><span class="lnt"> 8
</span><span class="lnt"> 9
</span><span class="lnt">10
</span><span class="lnt">11
</span><span class="lnt">12
</span><span class="lnt">13
</span><span class="lnt">14
</span><span class="lnt">15
</span><span class="lnt">16
</span><span class="lnt">17
</span><span class="lnt">18
</span><span class="lnt">19
</span><span class="lnt">20
</span><span class="lnt">21
</span><span class="lnt">22
</span><span class="lnt">23
</span><span class="lnt">24
</span><span class="lnt">25
</span><span class="lnt">26
</span><span class="lnt">27
</span><span class="lnt">28
</span><span class="lnt">29
</span><span class="lnt">30
</span><span class="lnt">31
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">void</span> <span class="nf">searchState</span><span class="p">(</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">ItemState</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">states</span><span class="p">)</span>
<span class="p">{</span>
	<span class="kt">int</span> <span class="n">act</span><span class="p">;</span>
	<span class="n">ItemState</span> <span class="n">current</span> <span class="o">=</span> <span class="n">states</span><span class="p">.</span><span class="n">back</span><span class="p">();</span>
	<span class="k">if</span><span class="p">(</span><span class="n">current</span><span class="p">.</span><span class="n">isFinalState</span><span class="p">())</span>
	<span class="p">{</span>
		<span class="n">printResult</span><span class="p">(</span><span class="n">states</span><span class="p">);</span>
		<span class="k">return</span><span class="p">;</span>
	<span class="p">}</span>
	<span class="k">for</span><span class="p">(</span><span class="n">act</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">act</span> <span class="o">&lt;</span> <span class="n">INVALID_ACTION_NAME</span><span class="p">;</span> <span class="n">act</span><span class="o">++</span><span class="p">)</span>
	<span class="p">{</span>
		<span class="c1">//debug_out &lt;&lt; act &lt;&lt;endl;
</span><span class="c1"></span>		<span class="n">searchStateOnOneAction</span><span class="p">(</span><span class="n">states</span><span class="p">,</span> <span class="n">current</span><span class="p">,</span> <span class="n">actEffect</span><span class="p">[</span><span class="n">act</span><span class="p">]);</span>
	<span class="p">}</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">searchStateOnOneAction</span><span class="p">(</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">ItemState</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">states</span><span class="p">,</span> <span class="n">ItemState</span> <span class="o">&amp;</span><span class="n">current</span><span class="p">,</span> <span class="n">ACTION_EFFECTION</span><span class="o">&amp;</span> <span class="n">actEff</span><span class="p">)</span>
<span class="p">{</span>
	<span class="n">ItemState</span> <span class="n">next</span><span class="p">;</span>
	<span class="kt">bool</span> <span class="n">canTackAction</span><span class="p">;</span>
	<span class="n">canTackAction</span> <span class="o">=</span> <span class="n">current</span><span class="p">.</span><span class="n">takeAction</span><span class="p">(</span><span class="n">next</span><span class="p">,</span> <span class="n">actEff</span><span class="p">);</span>
	<span class="c1">//debug_out &lt;&lt; next;
</span><span class="c1"></span>	<span class="k">if</span><span class="p">(</span><span class="n">canTackAction</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">isProcessed</span><span class="p">(</span><span class="n">states</span><span class="p">,</span> <span class="n">next</span><span class="p">))</span>
	<span class="p">{</span>
		<span class="c1">//debug_out &lt;&lt; &#34;valid&#34; &lt;&lt; endl;
</span><span class="c1"></span>		<span class="c1">// printResult(states);
</span><span class="c1"></span>		<span class="n">states</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">next</span><span class="p">);</span>
		<span class="n">searchState</span><span class="p">(</span><span class="n">states</span><span class="p">);</span>
		<span class="n">states</span><span class="p">.</span><span class="n">pop_back</span><span class="p">();</span>
	<span class="p">}</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><p>两个函数起到了递归的作用，同时使用deque避免出现环路</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt">1
</span><span class="lnt">2
</span><span class="lnt">3
</span><span class="lnt">4
</span><span class="lnt">5
</span><span class="lnt">6
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">bool</span> <span class="nf">isProcessed</span><span class="p">(</span><span class="n">deque</span><span class="o">&lt;</span><span class="n">ItemState</span><span class="o">&gt;</span> <span class="o">&amp;</span><span class="n">states</span><span class="p">,</span> <span class="n">ItemState</span><span class="o">&amp;</span> <span class="n">state</span><span class="p">)</span>
<span class="p">{</span>
	<span class="k">auto</span> <span class="n">it</span> <span class="o">=</span> <span class="n">states</span><span class="p">.</span><span class="n">end</span><span class="p">();</span>
	<span class="n">it</span> <span class="o">=</span> <span class="n">find_if</span><span class="p">(</span><span class="n">states</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span> <span class="n">states</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span> <span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="n">ItemState</span><span class="o">&amp;</span> <span class="n">s</span><span class="p">){</span><span class="k">return</span> <span class="n">s</span><span class="o">==</span><span class="n">state</span><span class="p">;});</span>
	<span class="k">return</span><span class="p">(</span><span class="n">it</span><span class="o">!=</span><span class="n">states</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
<span class="p">}</span>
</code></pre></td></tr></table>
</div>
</div><p>完整代码见https://github.com/lclei/algorithm_fun/tree/master/MonkAndMonster</p>
<p>最后的找到了四种方案</p>
<div class="highlight"><div class="chroma">
<table class="lntable"><tr><td class="lntd">
<pre class="chroma"><code><span class="lnt">  1
</span><span class="lnt">  2
</span><span class="lnt">  3
</span><span class="lnt">  4
</span><span class="lnt">  5
</span><span class="lnt">  6
</span><span class="lnt">  7
</span><span class="lnt">  8
</span><span class="lnt">  9
</span><span class="lnt"> 10
</span><span class="lnt"> 11
</span><span class="lnt"> 12
</span><span class="lnt"> 13
</span><span class="lnt"> 14
</span><span class="lnt"> 15
</span><span class="lnt"> 16
</span><span class="lnt"> 17
</span><span class="lnt"> 18
</span><span class="lnt"> 19
</span><span class="lnt"> 20
</span><span class="lnt"> 21
</span><span class="lnt"> 22
</span><span class="lnt"> 23
</span><span class="lnt"> 24
</span><span class="lnt"> 25
</span><span class="lnt"> 26
</span><span class="lnt"> 27
</span><span class="lnt"> 28
</span><span class="lnt"> 29
</span><span class="lnt"> 30
</span><span class="lnt"> 31
</span><span class="lnt"> 32
</span><span class="lnt"> 33
</span><span class="lnt"> 34
</span><span class="lnt"> 35
</span><span class="lnt"> 36
</span><span class="lnt"> 37
</span><span class="lnt"> 38
</span><span class="lnt"> 39
</span><span class="lnt"> 40
</span><span class="lnt"> 41
</span><span class="lnt"> 42
</span><span class="lnt"> 43
</span><span class="lnt"> 44
</span><span class="lnt"> 45
</span><span class="lnt"> 46
</span><span class="lnt"> 47
</span><span class="lnt"> 48
</span><span class="lnt"> 49
</span><span class="lnt"> 50
</span><span class="lnt"> 51
</span><span class="lnt"> 52
</span><span class="lnt"> 53
</span><span class="lnt"> 54
</span><span class="lnt"> 55
</span><span class="lnt"> 56
</span><span class="lnt"> 57
</span><span class="lnt"> 58
</span><span class="lnt"> 59
</span><span class="lnt"> 60
</span><span class="lnt"> 61
</span><span class="lnt"> 62
</span><span class="lnt"> 63
</span><span class="lnt"> 64
</span><span class="lnt"> 65
</span><span class="lnt"> 66
</span><span class="lnt"> 67
</span><span class="lnt"> 68
</span><span class="lnt"> 69
</span><span class="lnt"> 70
</span><span class="lnt"> 71
</span><span class="lnt"> 72
</span><span class="lnt"> 73
</span><span class="lnt"> 74
</span><span class="lnt"> 75
</span><span class="lnt"> 76
</span><span class="lnt"> 77
</span><span class="lnt"> 78
</span><span class="lnt"> 79
</span><span class="lnt"> 80
</span><span class="lnt"> 81
</span><span class="lnt"> 82
</span><span class="lnt"> 83
</span><span class="lnt"> 84
</span><span class="lnt"> 85
</span><span class="lnt"> 86
</span><span class="lnt"> 87
</span><span class="lnt"> 88
</span><span class="lnt"> 89
</span><span class="lnt"> 90
</span><span class="lnt"> 91
</span><span class="lnt"> 92
</span><span class="lnt"> 93
</span><span class="lnt"> 94
</span><span class="lnt"> 95
</span><span class="lnt"> 96
</span><span class="lnt"> 97
</span><span class="lnt"> 98
</span><span class="lnt"> 99
</span><span class="lnt">100
</span><span class="lnt">101
</span><span class="lnt">102
</span><span class="lnt">103
</span><span class="lnt">104
</span><span class="lnt">105
</span><span class="lnt">106
</span><span class="lnt">107
</span><span class="lnt">108
</span><span class="lnt">109
</span><span class="lnt">110
</span><span class="lnt">111
</span><span class="lnt">112
</span><span class="lnt">113
</span><span class="lnt">114
</span><span class="lnt">115
</span><span class="lnt">116
</span><span class="lnt">117
</span><span class="lnt">118
</span><span class="lnt">119
</span><span class="lnt">120
</span><span class="lnt">121
</span><span class="lnt">122
</span><span class="lnt">123
</span><span class="lnt">124
</span><span class="lnt">125
</span><span class="lnt">126
</span><span class="lnt">127
</span><span class="lnt">128
</span><span class="lnt">129
</span><span class="lnt">130
</span><span class="lnt">131
</span><span class="lnt">132
</span><span class="lnt">133
</span><span class="lnt">134
</span><span class="lnt">135
</span><span class="lnt">136
</span><span class="lnt">137
</span><span class="lnt">138
</span><span class="lnt">139
</span><span class="lnt">140
</span><span class="lnt">141
</span><span class="lnt">142
</span><span class="lnt">143
</span><span class="lnt">144
</span><span class="lnt">145
</span><span class="lnt">146
</span><span class="lnt">147
</span><span class="lnt">148
</span><span class="lnt">149
</span><span class="lnt">150
</span><span class="lnt">151
</span><span class="lnt">152
</span><span class="lnt">153
</span><span class="lnt">154
</span><span class="lnt">155
</span><span class="lnt">156
</span><span class="lnt">157
</span><span class="lnt">158
</span><span class="lnt">159
</span><span class="lnt">160
</span><span class="lnt">161
</span><span class="lnt">162
</span><span class="lnt">163
</span><span class="lnt">164
</span><span class="lnt">165
</span><span class="lnt">166
</span><span class="lnt">167
</span><span class="lnt">168
</span><span class="lnt">169
</span><span class="lnt">170
</span><span class="lnt">171
</span><span class="lnt">172
</span><span class="lnt">173
</span><span class="lnt">174
</span><span class="lnt">175
</span><span class="lnt">176
</span><span class="lnt">177
</span><span class="lnt">178
</span><span class="lnt">179
</span><span class="lnt">180
</span><span class="lnt">181
</span><span class="lnt">182
</span><span class="lnt">183
</span><span class="lnt">184
</span><span class="lnt">185
</span><span class="lnt">186
</span><span class="lnt">187
</span><span class="lnt">188
</span><span class="lnt">189
</span><span class="lnt">190
</span><span class="lnt">191
</span><span class="lnt">192
</span><span class="lnt">193
</span><span class="lnt">194
</span><span class="lnt">195
</span></code></pre></td>
<td class="lntd">
<pre class="chroma"><code class="language-fallback" data-lang="fallback">o stands for monk, and x stands for monster.
3o  ||  0o
3x  ||  0x
boat||    

3o  ||  0o
1x  ||  2x
    ||boat

3o  ||  0o
2x  ||  1x
boat||    

3o  ||  0o
0x  ||  3x
    ||boat

3o  ||  0o
1x  ||  2x
boat||    

1o  ||  2o
1x  ||  2x
    ||boat

2o  ||  1o
2x  ||  1x
boat||    

0o  ||  3o
2x  ||  1x
    ||boat

0o  ||  3o
3x  ||  0x
boat||    

0o  ||  3o
1x  ||  2x
    ||boat

0o  ||  3o
2x  ||  1x
boat||    

0o  ||  3o
0x  ||  3x
    ||boat

o stands for monk, and x stands for monster.
3o  ||  0o
3x  ||  0x
boat||    

3o  ||  0o
1x  ||  2x
    ||boat

3o  ||  0o
2x  ||  1x
boat||    

3o  ||  0o
0x  ||  3x
    ||boat

3o  ||  0o
1x  ||  2x
boat||    

1o  ||  2o
1x  ||  2x
    ||boat

2o  ||  1o
2x  ||  1x
boat||    

0o  ||  3o
2x  ||  1x
    ||boat

0o  ||  3o
3x  ||  0x
boat||    

0o  ||  3o
1x  ||  2x
    ||boat

1o  ||  2o
1x  ||  2x
boat||    

0o  ||  3o
0x  ||  3x
    ||boat

o stands for monk, and x stands for monster.
3o  ||  0o
3x  ||  0x
boat||    

2o  ||  1o
2x  ||  1x
    ||boat

3o  ||  0o
2x  ||  1x
boat||    

3o  ||  0o
0x  ||  3x
    ||boat

3o  ||  0o
1x  ||  2x
boat||    

1o  ||  2o
1x  ||  2x
    ||boat

2o  ||  1o
2x  ||  1x
boat||    

0o  ||  3o
2x  ||  1x
    ||boat

0o  ||  3o
3x  ||  0x
boat||    

0o  ||  3o
1x  ||  2x
    ||boat

0o  ||  3o
2x  ||  1x
boat||    

0o  ||  3o
0x  ||  3x
    ||boat

o stands for monk, and x stands for monster.
3o  ||  0o
3x  ||  0x
boat||    

2o  ||  1o
2x  ||  1x
    ||boat

3o  ||  0o
2x  ||  1x
boat||    

3o  ||  0o
0x  ||  3x
    ||boat

3o  ||  0o
1x  ||  2x
boat||    

1o  ||  2o
1x  ||  2x
    ||boat

2o  ||  1o
2x  ||  1x
boat||    

0o  ||  3o
2x  ||  1x
    ||boat

0o  ||  3o
3x  ||  0x
boat||    

0o  ||  3o
1x  ||  2x
    ||boat

1o  ||  2o
1x  ||  2x
boat||    

0o  ||  3o
0x  ||  3x
    ||boat
</code></pre></td></tr></table>
</div>
</div>
    </div>

    <div class="post-copyright">
  <p class="copyright-item">
    <span class="item-title">Author</span>
    <span class="item-content">lclei</span>
  </p>
  <p class="copyright-item">
    <span class="item-title">LastMod</span>
    <span class="item-content">
        2019-12-08
        
    </span>
  </p>
  
  
</div>
<footer class="post-footer">
      <div class="post-tags">
          <a href="/tags/algorithm/">algorithm</a>
          <a href="/tags/cpp/">cpp</a>
          </div>
      <nav class="post-nav">
        <a class="prev" href="/post/docker3/">
            <i class="iconfont icon-left"></i>
            <span class="prev-text nav-default">docker3</span>
            <span class="prev-text nav-mobile">Prev</span>
          </a>
        <a class="next" href="/post/hello-world/">
            <span class="next-text nav-default">Hello World</span>
            <span class="next-text nav-mobile">Next</span>
            <i class="iconfont icon-right"></i>
          </a>
      </nav>
    </footer>
  </article>
        </div>
        

  

  

      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="social-links">
      <a href="mailto:lclei@mail.ustc.edu.cn" class="iconfont icon-email" title="email"></a>
      <a href="https://gitee.com/lclei" class="iconfont icon-gitee" title="gitee"></a>
      <a href="https://gitee.com/lclei" class="iconfont icon-github" title="github"></a>
  <a href="http://localhost:1313/index.xml" type="application/rss+xml" class="iconfont icon-rss" title="rss"></a>
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - 
    <a class="theme-link" href="https://github.com/olOwOlo/hugo-theme-even">Even</a>
  </span>

  

  <span class="copyright-year">
    &copy; 
    2018 - 
    2022<span class="heart"><i class="iconfont icon-heart"></i></span><span>lclei</span>
  </span>
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont icon-up"></i>
    </div>
  </div>
  
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.2.1/dist/jquery.min.js" integrity="sha256-hwg4gsxgFZhOsEEamdOYGBf13FyQuiTwlAQgxVSNgt4=" crossorigin="anonymous"></script>
  <script src="https://cdn.jsdelivr.net/npm/slideout@1.0.1/dist/slideout.min.js" integrity="sha256-t+zJ/g8/KXIJMjSVQdnibt4dlaDxc9zXr/9oNPeWqdg=" crossorigin="anonymous"></script>
  <script src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@3.1.20/dist/jquery.fancybox.min.js" integrity="sha256-XVLffZaxoWfGUEbdzuLi7pwaUJv1cecsQJQqGLe7axY=" crossorigin="anonymous"></script>



<script type="text/javascript" src="/js/main.min.c12618f9a600c40bd024996677e951e64d3487006775aeb22e200c990006c5c7.js"></script>








</body>
</html>
